// 1. 遍历 hash
// 把每个相同的元素，作为hash的key，出现的此说作为hash的值。
// 只要 当前元素的个数超过了n/2，那么他就是最多的数
function majorityElement(nums: number[]): number {
    let map = new Map();
    let halfLen = Math.ceil(nums.length / 2);
    for (let i of nums) {
        map.get(i) ? map.set(i, map.get(i) + 1) : map.set(i, 1);
        if (map.get(i) === halfLen) {
            return i;
        }
    }
};

// 2. 排序法，众数位 n/2位置的元素
function majorityElement1(nums: number[]): number {
    nums.sort((a, b) => a - b);
    return nums[Math.floor(nums.length / 2)];
};

// 3 摩尔投票法
// 思路： 
// 1.设置候选人candidate为nums[0],设置票数count为1
// 如果票数为0，则把当前遍历的元素作为新的候选人。
// 如果遇到与candidate相同的元素，则count票数加1
// 如果遇到与candidate 不同的元素，则count票数减去1
// 由于最终candidate的数量时大于n/2的，所以最后剩下的candidate一定是数量最多的元素。
function majorityElement3(nums: number[]): number {
    let count = 0;
    let candidate;
    for (let num of nums) {
        if (count === 0) candidate = num;
        count += candidate === num ? 1 : -1;
    }
    return candidate;
};

// 4. 分治算法
// 思路： 如果a是众数，那么，把nums分成两部分，那么a至少是其中一部分的众数。
// 反证明法，
// 如果a是nums的众数，单a既不是左边,也不是右边的众数。那么一定有a < (left/2 +right/2)
// 而 (left/2 +right/2) <= (left+right)/2 ,
// 则说明a 也不是 nums的众数，和前提条件a是nums的众数不同。

function majorityElement4(nums: number[]): number {

    const divideConquer = function (nums: number[], low: number, height: number): number {
        // 1. terminator
        if (low === height) {
            return nums[low]
        }
        // 2. split problems  3. drill down
        let mid: number = Math.floor(nums.length / 2)
        let leftResult: number = divideConquer(nums.slice(0, mid), 0, mid-1)
        let rightResult: number = divideConquer(nums.slice(mid), 0, nums.length-mid-1)

        // 4. merge subresult
        // 如果左右相同，那么就返回left就行
        if (leftResult === rightResult) {
            return leftResult
        }
        // 判断leftResult，rightResult再整个nums的数量，多的返回
        let leftAllTimes = nums.reduce((pre, curr) => curr === leftResult ? pre + 1 : pre, 0)
        let rightAllTimes = nums.reduce((pre, curr) => curr === rightResult ? pre + 1 : pre, 0)
        return leftAllTimes > rightAllTimes ? leftResult : rightResult
        // 5. reverse state
    }
   return divideConquer(nums,0,nums.length-1)
};
